<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，
        // 原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
        // 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

        // 方法一 数个数
        // var sortColors = function (nums) {
        //     let one = 0,
        //         two = 0,
        //         three = 0;
        //     for (let i = 0; i < nums.length; i++) {
        //         if (nums[i] == 0) {
        //             one++;
        //         } else if (nums[i] == 1) {
        //             two++;
        //         } else {
        //             three++;
        //         }
        //     }

        //     for (let i = 0; i < one; i++) {
        //         nums[i] = 0;
        //     }

        //     for (let i = 0; i < two; i++) {
        //         nums[one + i] = 1;
        //     }

        //     for (let i = 0; i < three; i++) {
        //         nums[one + two + i] = 2;
        //     }
        //     return nums;
        // }

        // 方法二 单指针
        // 第一次遍历：将所有0交换到数组的头部；
        // 第二次遍历：将数组所有的1交换到头部的0之后；
        // 此时，所有的2都出现在了数组的尾部。
        // var sortColors = function (nums) {
        //     let ptr = 0;

        //     for (let i = 0; i < nums.length; i++) {
        //         if (nums[i] == 0) {
        //             let temp = nums[i];
        //             nums[i] = nums[ptr];
        //             nums[ptr] = temp;
        //             ptr++;
        //         }
        //     }

        //     for (let i = 0; i < nums.length; i++) {
        //         if (nums[i] == 1) {
        //             let temp = nums[i];
        //             nums[i] = nums[ptr];
        //             nums[ptr] = temp;
        //             ptr++;
        //         }
        //     }

        //     return nums;
        // }

        // 方法三 双指针  --  额外使用一个指针来分别交换0和1
        // 没实现！！！！！
        var sortColors = function (nums) {
            let n = nums.length;
            let p0 = 0,
                p1 = 0;

            for (let i = 0; i < n; i++) {
                if (nums[i] == 1) {
                    let temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                    p1++;
                } else if (nums[i] == 0) {
                    let temp = nums[i];
                    nums[i] = nums[p0];
                    nums[p0] = temp;
                    if (p0 < p1) {
                        let temp = nums[i];
                        nums[i] = nums[p1];
                        nums[p1] = temp;
                    }
                    p0++;
                    p1++;
                }
            }
        }


        console.log(sortColors([2, 0, 2, 1, 1, 0]));
    </script>
</body>

</html>